#include <iostream>
#include <queue>
using namespace std;

typedef struct Node {
  int data;
  Node *l, *r;
} * BiTree;

/**
 * @brief 建树
 *
 */
BiTree create() {
  int x;
  cin >> x;
  if (x == -1) {
    return nullptr;
  } else {
    BiTree t = new Node;
    t->data = x;
    t->l = create();
    t->r = create();
    return t;
  }
}

/**
 * @brief 先序遍历
 */
void preOrder(BiTree t) {
  if (t) {
    cout << t->data << " ";
    preOrder(t->l);
    preOrder(t->r);
  }
}

/**
 * @brief 中序遍历
 */
void inOrder(BiTree t) {
  if (t) {
    inOrder(t->l);
    cout << t->data << " ";
    inOrder(t->r);
  }
}

/**
 * @brief 后序遍历
 */
void postOrder(BiTree t) {
  if (t) {
    postOrder(t->l);
    postOrder(t->r);
    cout << t->data << " ";
  }
}

/**
 * @brief 层次遍历
 *
 * @return int
 */
void levelOrder(BiTree t) {
  if (t == nullptr) {
    return;
  }

  queue<BiTree> q;
  // 将根节点放入队头
  q.push(t);
  while (!q.empty()) {
    cout << q.front()->data << " ";
    if (q.front()->l)
      q.push(q.front()->l);
    if (q.front()->r)
      q.push(q.front()->r);
    q.pop();
  }
}

int main() {
  // 1 2 4 -1 -1 5 -1 -1 3 6 -1 -1 7 -1 -1
  BiTree root = create();

  preOrder(root);
  cout << endl;

  inOrder(root);
  cout << endl;

  postOrder(root);
  cout << endl;

  levelOrder(root);
  cout << endl;
  return 0;
}
